Problem statement: zenit13kkj

Toto zadanie obsahuje prísne dôverné informácie. Tým, že ho začnete čítať súhlasíte, že tieto informácie nikdy a za žiadných okolností neprezradíte¹.

Americká NSA sa rozhodla, že niektoré informácie medzinárodného významu zašifruje takzvaným prezidentským distribuovaným algoritmom. Detaily tohto postupu nemôžeme uviesť. Pre nás je dôležité, že niektorí prezidenti sveta dostali krátku časť hesla. Dešifrovanie nie je možné uskutočniť bez toho, aby ste mali všetky časti hesla. Ako správne tušíte, aj Maroško je jedným z vyvolených prezidentov.

Maroškova časť hesla má dĺžku N a je vo forme postupnosti čísel od 1 po N. Každé z týchto čísel je v postupnosti práve raz (učenejšie povedané, časť hesla je permutácia rádu N).

Dnes ráno Maroško zistil, že sa mu z nohavíc stratil papierik s touto postupnosťou. Aby sa predišlo obrovskému medzinárodnému škandálu, pomôžte mu a skúste permutáciu zrekonštruovať. Kópia permutácie sa samozrejme nikde na svete nenachádza. Expertom zo SIS² sa ale podarilo zistiť takzvanú kontrolnú postupnosť. Uvažujme nasledovný pseudokód (pascalovská verzia):

function merge_sort(arr):
    n = arr.length()
    if n <= 1:
        return arr

    // arr is indexed 0 through n-1, inclusive
    mid = floor(n/2)
    
    first_half = merge_sort(arr[0..mid-1])
    second_half = merge_sort(arr[mid..n-1])
    return merge(first_half, second_half)

function merge(arr1, arr2):
    result = []
    while arr1.length() > 0 and arr2.length() > 0:
        if arr1[0] < arr2[0]:
            print '1' // kontrolny vypis
            result.append(arr1[0])
            arr1.remove_first()
        else:
            print '2' // kontrolny vypis
            result.append(arr2[0])
            arr2.remove_first()
            
    result.append(arr1)
    result.append(arr2)
    return result

Tento kód je štandardná implementácia známeho triediaceho algoritmu Mergesort. Všimnite si kontrolné výpisy znakov 1 a 2. Hackerský tím SIS sa nabúral do amerických servrov, o ktorých nikto nevie, že existujú. Okrem zdrojového kódu vyššie sa mu podarilo zistiť aj tajný kontrolný výpis tohto algoritmu, ak mu dáme ako vstup Maroškovu permutáciu. Vieme Maroškovu permutáciu z tohto kontrolného výpisu spätne zrekonštruovať?

Na prvom riadku vstupu je dĺžka Maroškovej permutácie N (2 ≤ N ≤ 10,000). Na druhom riadku je reťazec pozostávajúci zo znakov 1 a 2. Tento reťazec je neprázdny a nebude dlhší ako 200,000 znakov. Môžete predpokladať, že naozaj existuje korektná permutácia dĺžky N taká, že kontrolný výstup jej spracovania programom vyššie ste dostali na vstupe. Na jediný riadok výstupu vypíšte hľadanú permutáciu. Medzi každými dvoma číslami vypíšte jednu medzeru. Môžete predpokladať, že výstup je jednoznačný.

2
1 

1 2 

2
2 

2 1 

4
12212 

2 4 3 1 

10
121221212111122121212 

6 10 1 8 4 2 3 5 9 7 

Footnotes: